#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
bool canPartition(vector<int> &nums)
{
    int sum = 0;
    for (int num : nums)
    {
        sum += num;
    }
    if (sum & 1)
        return false;
    vector<vector<bool>> dp(nums.size(), vector<bool>((sum >>= 1) + 1, false));
    for (int i = 0; i < nums.size(); i++)
    {
        for (int j = 0; j <= sum; j++)
        {
            if (!i)
                dp[i][j] = (nums[i] == j);
            else
                dp[i][j] = dp[i - 1][j] || (j - nums[i] >= 0 ? dp[i - 1][j - nums[i]] : false);
        }
    }
    return dp[nums.size() - 1][sum];
}